package com.cn.algorithm02.class08;

import com.cn.algorithm02.class01.CodeUtil;

import java.util.Map;

/***
 * @author: hels
 * @description: 基数排序，通过桶排序思想实现。
 * 适用于非负整数
 ** 时间复杂度为O(N*log[10]digit) digit为最大数位数
 * **/
public class C03_RadixSort {
    public static void main(String[] args) {
        int[] arr = {88882,23,12,4212,1234,132,21,1,3,41};
        radixSort(arr, 0, arr.length - 1, maxDigit(arr));
        CodeUtil.printArray(arr);
    }

    /*
    arr[L..R] 待排序数组范围，digit为最大数的十进制位数
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        if (arr == null || arr.length < 2) return;

        int[] help = new int[arr.length];
        for (int d = 1; d <= digit; d++) {
            int[] count = new int[10];
            // 1 遍历第digit位上的数字进行数组计数
            for (int j = L; j <= R; j++) {
                int index = getDigit(arr[j], d);
                count[index]++;
            }

            // 2 遍历count计算累加和 -> 界定统计位数的数字在那个范围上
            for (int j = 1; j < count.length; j++) {
                count[j] = count[j - 1] + count[j];
            }

            // 3 从右往左进行排序
            for (int j = R; j >= L; j--) {
                int index = getDigit(arr[j], d);
                help[count[index] - 1] = arr[j];
                count[index]--;
            }

            // 4 将help数组深拷贝到arr数组中
            for (int i = 0; i < arr.length; i++) {
                arr[L + i] = help[i];
            }

        }
    }

    public static int maxDigit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = i > max ? i : max;
        }
        int ans = 0;
        while (max != 0) {
            ans++;
            max = max / 10;
        }
        return ans;
    }

    /*
     // ((x / ((int) Math.pow(10, d - 1))) % 10)
        // 取某个数字从个位开始第几位的数字
        int num = 321;
        System.out.println((num / (int) Math.pow(10, 0))%10);  -> 1
        System.out.println((num / (int) Math.pow(10, 1))%10);  -> 2
        System.out.println((num / (int) Math.pow(10, 2))%10);  -> 3
    */
    private static int getDigit(int number, int i) {
        return (number / (int) Math.pow(10, i - 1)) % 10;
    }
}
